package alo.p11.work;

/**
 * @ClassName BinarySearchOccurrence
 * @Description 有序数组某元素首次和最后一次出现的索引
 * @Author Fanxc
 * @DATE 2021/3/14 9:47
 * @Version 1.0
 */
public class BinarySearchOccurrence {
    //寻找首次出现的索引
    int binarySearchFirstOccurrence(int[] A,int low,int high,int data){
        if (high>low){
            int mid=low+(high-low)/2;
            if((mid==low&&A[mid]==data) || (A[mid]==data&&A[mid-1]<data)){
                return mid;
            }else if (A[mid]>=data){
                return binarySearchFirstOccurrence(A,low,mid-1,data);
            }else return binarySearchFirstOccurrence(A,mid+1,high,data);
        }
        return -1;
    }
    //出现的最后一次索引
    int binarySearchLastOccurrence(int[] A,int low,int high,int data){
        if (high>low){
            int mid=low+(high-low)/2;
            if((mid==high&&A[mid]==data) || (A[mid]==data&&A[mid+1]<data)){
                return mid;
            }else if (A[mid]<=data){
                return binarySearchFirstOccurrence(A,mid+1,high,data);
            }else return binarySearchFirstOccurrence(A,low,mid-1,data);
        }
        return -1;
    }
}
